relativized complexity class

Definition (relativized complexity class)

For complexity class and language $A$, let relativized complexity class $C^A$ be the languages decidable by $C$-machines with oracle access to $A$.

Definition (relativized world)

A relativized world, i.e. a world relative to oracle $A$, is one in which every machine has access to the same oracle.

See also

• Baker-Gill-Solovay theorem

References

1. https://faculty.cc.gatech.edu/~ladha/toc/L21.pdf